package cc.magicjson.example.demo.tsp;

import java.util.Arrays;

public class DynamicProgrammingTSP {
    private static final int INF = 1000000000; // 用于表示无限大的值（无法达到）
    private int[][] dp; // 动态规划表，用于存储子问题的解
    private int[][] dist; // 距离矩阵
    private int n; // 城市数量

    public DynamicProgrammingTSP(int[][] dist) {
        this.n = dist.length; // 初始化城市数量
        this.dist = dist; // 初始化距离矩阵
        this.dp = new int[1 << n][n]; // 初始化动态规划表，大小为2^n * n
        for (int[] row : dp) {
            Arrays.fill(row, -1); // 将动态规划表中的每个值初始化为-1，表示未计算
        }
    }

    // 动态规划求解TSP问题的递归函数
    private int tsp(int mask, int pos) {
        // 基本情况：如果所有城市都被访问过，则返回当前城市到起点的距离
        if (mask == (1 << n) - 1) {
            return dist[pos][0];
        }

        // 如果这个子问题已经计算过，直接返回存储的结果
        if (dp[mask][pos] != -1) {
            return dp[mask][pos];
        }

        int ans = INF; // 初始化当前子问题的最优解为无限大
        // 尝试去所有其他未访问的城市，选择最短路径
        for (int city = 0; city < n; city++) {
            if ((mask & (1 << city)) == 0) { // 如果城市city还未访问
                int newAns = dist[pos][city] + tsp(mask | (1 << city), city); // 计算去该城市后的路径长度
                ans = Math.min(ans, newAns); // 选择最小的路径长度作为当前子问题的解
            }
        }
        return dp[mask][pos] = ans; // 存储并返回当前子问题的解
    }

    // 包装函数，用于开始TSP求解
    public int findShortestPath() {
        return tsp(1, 0); // 从起点城市（0）开始，并且已访问起点（mask=1）
    }

    public static void main(String[] args) {
        int[][] dist = {
                {0, 10, 15, 20},  // 城市间的距离矩阵
                {10, 0, 35, 25},
                {15, 35, 0, 30},
                {20, 25, 30, 0}
        };

        DynamicProgrammingTSP dpTSP = new DynamicProgrammingTSP(dist); // 创建动态规划算法实例
        System.out.println("动态规划算法计算的路径长度: " + dpTSP.findShortestPath()); // 输出计算结果
    }
}
